|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
06.02.2014, 10:38 | #1 |
Форумчанин
Регистрация: 04.06.2009
Сообщений: 351
|
Поиск оптимального пути из точки A в точку Б
Всем Привет!
Есть точки между которими есть связи (см. рисунок в прикреплении), нужно найти ВСЕ пути с точки "1" в точку "11" и выбрать оптимальный (путь в котором наименьшее кол. промежуточних точек) Есть 3 варианта: - первый: 1-2-3-4-5-6-11 - второй: 1-2-3-4-8-11 - третий: 1-2-3-8-11 (оптимальный) - точки НЕ должни повторяться чтоб не было зацыкливания - кол. точек и связей между ними будет меняться и расширяться Как реализовать? Помница на "вышке" изучали графы, там что-то было похожее, но не уверен. Может есть готовое решение? Помогите реализовать
Мне разрешено открывать только одну страницу - about :blank. Сперва было скучно, но потом я втянулся. Теперь у меня там живет 2 виртуальных друга, и я слышу голоса из розетки!
Последний раз редактировалось spirit-ua; 06.02.2014 в 10:58. |
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 |
Форумчанин
Регистрация: 04.06.2009
Сообщений: 351
|
Неправильная постановка задачи...
Я не предусмотрел что ребра графа могут быть разной длины... следовательно: 1. Волновой алгоритм, из прочитаной мной литературы, ищет кратчайший путь в графе с рёбрами единичной длины что решает вопрос по вхождению минимального кол. промежуточных точек 2. Почитал про алгоритм Беллмана-Форда и Де́йкстры и, если я правильно понял, приведенный мною граф является графом типа "Дерево", и в графе не каждая вершина графа имеет "связь" с любой другой вершиной. Опять же, из того что я прочитал, для даного случая оптимальней алгоритм "Дейкстры". Господа, подскажите, алгоритм "Дейкстры" более оптимальный для даной задачи и по какому алгоритму легче реализовать задачу? Я не супер-мега-прог-мер, есть только основные понятия и базовые знания программирования
Мне разрешено открывать только одну страницу - about :blank. Сперва было скучно, но потом я втянулся. Теперь у меня там живет 2 виртуальных друга, и я слышу голоса из розетки!
Последний раз редактировалось spirit-ua; 07.02.2014 в 01:29. |
06.02.2014, 18:28 | #5 |
Участник клуба
Регистрация: 08.10.2007
Сообщений: 1,185
|
Так тут по заданию сначала надо найти все пути - в таком случае зачем все эти алгоритмы, если уже будет список всех путей? Просто рекурсия.
|
14.02.2014, 13:36 | #6 |
Форумчанин
Регистрация: 04.06.2009
Сообщений: 351
|
красными линиями отмечены все 4 (четыре) оптимальные пути из точки "1" в точку "6". В мемо получил обратную "связь" из точки "6" в точку "1" но относительно только "соседних" связаных точек, как скомпоновать и получить все четыре маршрута??? хоть к стенке ставьте - не могу догнать...
Подскажите
Мне разрешено открывать только одну страницу - about :blank. Сперва было скучно, но потом я втянулся. Теперь у меня там живет 2 виртуальных друга, и я слышу голоса из розетки!
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Нахождения оптимального пути | 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 |