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 могат да чакат едновременно.
- Кой път намира BFS и колко хода има той?
- Кой път намира DFS и каква е цената му?
- Кой път избира търсенето с равномерна цена и колко струва?
- Ако всички ходове струваха 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))
В речника Неинформирано търсене · Търсене с равномерна цена · Обхождане в ширина (BFS) · Обхождане в дълбочина (DFS).