133. Неинформирано търсене — BFS, DFS и равномерна цена

Неинформираното търсене използва зададените действия и цени. BFS предпочита по-малка дълбочина. DFS следва избрана посока. Търсенето с равномерна цена избира най-малката натрупана цена g. Тази стратегия намира най-евтин път в примера с положителни цени.

Раздел в разширената разработка.

Самостоятелна задача

Условие

Насочените преходи с цени са S→A (1), S→B (4), A→C (1), C→G (5), B→G (1). Началото е S, целта е G. BFS и DFS разглеждат A преди B, а целта се проверява при избор на път за обработка. Търсенето с равномерна цена избира път с най-ниска обща цена. Тук разглеждаме пътища в дърво на търсенето, затова два различни пътя до G могат да чакат едновременно.

  1. Кой път намира BFS и колко хода има той?
  2. Кой път намира DFS и каква е цената му?
  3. Кой път избира търсенето с равномерна цена и колко струва?
  4. Ако всички ходове струваха 1, каква щеше да е цената на пътя от BFS?

Отговори за самопроверка

Отговор 1

S→B→G, два хода.

Отговор 2

S→A→C→G, цена 7.

Отговор 3

S→B→G, цена 5.

Отговор 4

2.

Изпълним пример

Python 3. Сравни най-малко ходове с най-ниска цена. Всеки чакащ запис пази общата цена и пътя. При първото пускане избираме по дължината на пътя, при второто — по цената. min сравнява чакащите записи по избрания критерий.

roads = {
    "S": [("G", 7), ("A", 2)],
    "A": [("G", 2)]
}

def search(by_cost):
    waiting = [(0, "S")]
    while waiting:
        if by_cost:
            cost, path = min(waiting, key=lambda item: item[0])
        else:
            cost, path = min(waiting, key=lambda item: len(item[1]))
        waiting.remove((cost, path))
        if path[-1] == "G":
            return path, cost
        for next_stop, price in roads[path[-1]]:
            waiting.append((cost + price, path + next_stop))

print(*search(False))
print(*search(True))

Изтегли example.py.

В речника Неинформирано търсене · Търсене с равномерна цена · Обхождане в ширина (BFS) · Обхождане в дълбочина (DFS).