Поиск оптимального пути из точки A в точку Б - Общие вопросы Delphi

spirit-ua · 06.02.2014, 10:38

Всем Привет!

Есть точки между которими есть связи (см. рисунок в прикреплении), нужно найти ВСЕ пути с точки "1" в точку "11" и выбрать оптимальный (путь в котором наименьшее кол. промежуточних точек)

Есть 3 варианта:
- первый: 1-2-3-4-5-6-11
- второй: 1-2-3-4-8-11
- третий: 1-2-3-8-11 (оптимальный)

- точки НЕ должни повторяться чтоб не было зацыкливания
- кол. точек и связей между ними будет меняться и расширяться

Как реализовать? Помница на "вышке" изучали графы, там что-то было похожее, но не уверен.

Может есть готовое решение? Помогите реализовать

Пепел Феникса · 06.02.2014, 10:57

Алгоритм А* как пример.

Аватар · 06.02.2014, 11:01

алгоритм Беллмана-Форда
алгоритм Де́йкстры
Волновой алгоритм - скорее всего подойдет

spirit-ua · 06.02.2014, 14:23

Неправильная постановка задачи...

Я не предусмотрел что ребра графа могут быть разной длины... следовательно:
1. Волновой алгоритм, из прочитаной мной литературы, ищет кратчайший путь в графе с рёбрами единичной длины что решает вопрос по вхождению минимального кол. промежуточных точек
2. Почитал про алгоритм Беллмана-Форда и Де́йкстры и, если я правильно понял, приведенный мною граф является графом типа "Дерево", и в графе не каждая вершина графа имеет "связь" с любой другой вершиной. Опять же, из того что я прочитал, для даного случая оптимальней алгоритм "Дейкстры".

Господа, подскажите, алгоритм "Дейкстры" более оптимальный для даной задачи и по какому алгоритму легче реализовать задачу?
Я не супер-мега-прог-мер, есть только основные понятия и базовые знания программирования

Somebody · 06.02.2014, 18:28

Так тут по заданию сначала надо найти все пути - в таком случае зачем все эти алгоритмы, если уже будет список всех путей? Просто рекурсия.

spirit-ua · 14.02.2014, 13:36

красными линиями отмечены все 4 (четыре) оптимальные пути из точки "1" в точку "6". В мемо получил обратную "связь" из точки "6" в точку "1" но относительно только "соседних" связаных точек, как скомпоновать и получить все четыре маршрута??? хоть к стенке ставьте - не могу догнать...

Подскажите

06.02.2014, 10:57	#2
Пепел Феникса Старожил Регистрация: 28.01.2009 Сообщений: 21,000	Алгоритм А* как пример. Хорошо поставленный вопрос это уже половина ответа. \| Каков вопрос, таков ответ. Программа делает то что написал программист, а не то что он хотел. Функции/утилиты ждут в параметрах то что им надо, а не то что вы хотите.

06.02.2014, 11:01	#3
Аватар Старожил Регистрация: 17.11.2010 Сообщений: 18,922	алгоритм Беллмана-Форда алгоритм Де́йкстры Волновой алгоритм - скорее всего подойдет Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию

06.02.2014, 14:23	#4
spirit-ua Форумчанин Регистрация: 04.06.2009 Сообщений: 351	Неправильная постановка задачи... Я не предусмотрел что ребра графа могут быть разной длины... следовательно: 1. Волновой алгоритм, из прочитаной мной литературы, ищет кратчайший путь в графе с рёбрами единичной длины что решает вопрос по вхождению минимального кол. промежуточных точек 2. Почитал про алгоритм Беллмана-Форда и Де́йкстры и, если я правильно понял, приведенный мною граф является графом типа "Дерево", и в графе не каждая вершина графа имеет "связь" с любой другой вершиной. Опять же, из того что я прочитал, для даного случая оптимальней алгоритм "Дейкстры". Господа, подскажите, алгоритм "Дейкстры" более оптимальный для даной задачи и по какому алгоритму легче реализовать задачу? Я не супер-мега-прог-мер, есть только основные понятия и базовые знания программирования Мне разрешено открывать только одну страницу - about :blank. Сперва было скучно, но потом я втянулся. Теперь у меня там живет 2 виртуальных друга, и я слышу голоса из розетки! Последний раз редактировалось spirit-ua; 07.02.2014 в 01:29.

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Нахождения оптимального пути	linkoln_7	Общие вопросы C/C++	1	02.02.2014 00:18
Поиск оптимального решения	Lamborghini	Помощь студентам	4	12.10.2012 23:24
Нахождение оптимального пути в двумерном массиве	R.I.P. 666	Помощь студентам	1	07.11.2011 10:51
"Поиск оптимального пути движения снегоочистительных машин с учетом приоритета дорог" Пролог	Kvax	Помощь студентам	4	21.12.2008 22:18
Поиск оптимального решения	Uchiha	Общие вопросы Delphi	12	19.02.2008 23:04

06.02.2014, 18:28	#5
Somebody Участник клуба Регистрация: 08.10.2007 Сообщений: 1,185	Так тут по заданию сначала надо найти все пути - в таком случае зачем все эти алгоритмы, если уже будет список всех путей? Просто рекурсия.