Статьи

Алгоритм недели: кратчайший путь с Джикстра

Июнь 23, 2018

Сегодня вечером я решил, что мое учебное время будет сидеть и реализовывать алгоритм Джикстра в Python, чтобы помочь мне понять его. При написании решения такой проблемы я стараюсь не смотреть на другие решения, поэтому у меня не будет соблазна обмануть и пропустить шаги в процессе обучения. Надеюсь, это означает более подробное объяснение, а также код, который имеет больше смысла для кого-то, кто только учится.

Итак, сначала, что такое алгоритм «кратчайшего пути» и почему именно алгоритм Джикстры?

Алгоритмы кратчайшего пути легче всего связать с классом проблем, которые должен решать каждый онлайновый сервис управления движением (например, MapQuest или Google Maps). Эти проблемы работают с концепцией, известной как ориентированный взвешенный граф, который представляет собой набор точек со связями с другими точками, а также стоимость каждого соединения. Здесь это может помочь визуализировать это:

Представьте, что это упрощенная карта города. Каждый из обозначенных кругов является улицей пересечения. Линии, соединяющие их, являются улицами, а числа показывают, сколько времени требуется, чтобы добраться до каждого перекрестка с предыдущего.

Теперь, как можно быстрее, скажите мне, какой маршрут через город займет наименьшее количество времени?

Давайте использовать это как проблему, которую мы хотим решить.

Первые шаги

Мне нравится работать задом наперед и начать с того, что я ожидаю сделать, чтобы вызвать алгоритм. Мне нужно что-то вроде этого:

solution = find_shortest_path(graph, "A", "H")

Также нам нужно будет описать наш график в виде структуры данных. Я люблю JSON, поэтому давайте воспользуемся следующей самой близкой вещью в Python: словари. Это приведенный выше график:

graph = {
	"A": {
		"B": 1,
		"C": 2
	},
	"B": {
		"F": 6,
		"C": 1,
		"E": 3
	},
	"C": {
		"E": 4,
		"D": 2
	},
	"D": {
		"E": 1,
		"G": 4
	},
	"E": {
		"F": 2,
		"G": 2
	},
	"F": {
		"G": 1,
		"H": 11
	},
	"G": {
		"H": 14
	}
}

Это может быть прочитано как: «Путешествие от перекрестка A до перекрестка B занимает 1 минуту». «Путешествие от перекрестка А до перекрестка С занимает 2 минуты». «Путешествие от перекрестка B до перекрестка F занимает 6 минут». и т.п.

Если вы хотите перейти непосредственно к главному событию, мой готовый код здесь: https://gist.github.com/jcbozonier/5424673

Основная часть кода, которая также (удобно) объясняет процесс высокого уровня, состоит в следующем:

def find_shortest_path(graph, start_node, goal_node):
	paths = [{'path': [start_node], 'cost': 0}]
	while not something_reaches_goal(paths, goal_node):
	path = get_lowest_cost_path(paths)
	new_paths = get_nodes_and_costs(graph, path)
	paths.extend(new_paths)
	paths.remove(path)
	return get_path_that_reaches_goal(paths, goal_node)

Он начинается с создания пути по умолчанию на начальном узле.

Следующий шаг — проверить, есть ли у нас путь, который соединяется с целевым узлом, который также является нашим самым дешевым вариантом. Это возможно только в этом случае, если ваш начальный и целевой узел одинаковы. Затем мы получаем путь с наименьшей стоимостью из нашего списка путей и затем ищем этот узел, чтобы получить все пути, которые он составляет, вместе с их общими затратами. Мы добавляем эти пути в наш ранее существующий список путей, а затем удаляем только что исследованный нами путь.

Повторяйте этот абзац снова и снова, пока не найдете свое решение.

Копаем немного глубже

Я должен был понять, что ядром этой программы является большой список потенциальных путей, на которые нужно смотреть. Более «официальный» термин — «края», давайте не будем зацикливаться на этом. Так что да, у нас есть этот список потенциальных путей, с которыми связаны общие затраты, и мы в основном просто говорим: «Эй! Этот путь занимает меньше времени, чем другие. Интересно, будет ли это так, когда мы возьмем следующие перекрестки, с которыми это связано?

Таким образом, мы исследуем различные пересечения и одновременно только те пересечения, которые дадут нам наименьшее   возможное общее время.

Также обратите внимание, что как только мы изучим путь и обнаружим все связанные с ним пути, мы удалим его из нашего списка. Мы уже знаем, что это не оптимальный путь, потому что мы проверяем это перед тем, как начать каждую итерацию в нашем цикле. Если бы это был лучший путь, мы бы уже остановились.

В конкретных методах, которые составляют это общее представление об алгоритме, есть больше деталей, но они больше касаются реализации. Как только вы поймете, что на самом деле делает алгоритм галочкой, вы можете кодировать их так, как вам нравится.

Я ожидаю, что в нем есть ошибки, поскольку я еще не тестировал его с циклическими графиками. В любом случае я узнал кучу!

Наш окончательный ответ

О, да! Так каково решение нашей проблемы? Это вывод функции:

{'path': ['A', 'B', 'E', 'F', 'H'], 'cost': 17}

Так что A -> B -> E -> F -> H — самый быстрый маршрут со временем 17 минут.

Опять же, готовый код здесь:  https://gist.github.com/jcbozonier/5424673

Я также дал инструкции своему коду для объяснения каждого шага алгоритма здесь (остановитесь, он будет длинным): https://gist.github.com/jcbozonier/5424843

Примечание: все высказанные здесь мнения принадлежат мне, а не моему работодателю.

30
Share: