Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/2: Рейтинг темы: голосов - 2, средняя оценка - 5.00
Drulya
6 / 6 / 3
Регистрация: 24.09.2012
Сообщений: 231
Завершенные тесты: 2
1

Алгоритм поиска путей

11.02.2015, 12:09. Просмотров 473. Ответов 3
Метки нет (Все метки)

Привет. Ребята, такая тема, у меня есть граф, взвешенный, неориентированный, у меня есть пути из каждой вершины в каждую.
нужно в результате обойти все вершины, через 4,3 и 2 точки, кратчайшими путями, чтобы сумма всех путей через 4, через 3 и через две была минимальна(возможно это для вас очевидно, но простите незнающего).
Пример на картинке(точек намного больше)
Есть ли какой то алгоритм, я смотрел некоторые алгоритмы, но они для двух точек через все или топологическая соритировка, но у меня граф цикличный, подскажите, или есть у кого какие соображения, или у кого то попадалась такая задача. Спасибо
0
Миниатюры
Алгоритм поиска путей  
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.02.2015, 12:09
Ответы с готовыми решениями:

ищу алгоритм поиска путей
http://www.codewars.com/kata/paths-in-the-grid Представим, что нам дают прямоугольник,...

Алгоритм Флойда-Уоршелла [для нахождения кратчайших путей]
Дан ориентированный взвешенный граф. По его матрице смежности нужно для каждой пары вершин...

Алгоритм поиска
Привет всем.Вот тут задумался над алгоритмом поиска,смотрите я придумал такую схему:краулер обходит...

алгоритм поиска
помогите пожалуйста выбрать правильный ответ в алгоритме. Это тестовая задачка Для построения...

Алгоритм поиска информации
ПОИСК И ХРАНЕНИЕ ИНФОРМАЦИИ В СПРАВОЧНИКАХ Цель: Изучение основных принципов построения...

3
wingblack
281 / 255 / 45
Регистрация: 09.04.2013
Сообщений: 955
11.02.2015, 13:18 2
Ну, в небольших графах можно и перебором обойтись. Искать карты путей удовлетворяющие условию и выбирать где наименьшая сумма.
0
salam
189 / 170 / 29
Регистрация: 10.07.2012
Сообщений: 796
11.02.2015, 14:43 3
Цитата Сообщение от Drulya Посмотреть сообщение
нужно в результате обойти все вершины, через 4,3 и 2 точки, кратчайшими путями, чтобы сумма всех путей через 4, через 3 и через две была минимальна
что значит "через 4,3 и 2 точки"?

Добавлено через 9 минут
лучше будет, если вы предоставите максимально полную, строгую и очевидную формулировку задачи.
0
Drulya
6 / 6 / 3
Регистрация: 24.09.2012
Сообщений: 231
Завершенные тесты: 2
11.02.2015, 20:34  [ТС] 4
Точную формулировку не помню, но суть в том что в грузовик вмещает в себя до 4 ящиков, сколько надо грузовиков и как они проедут чтобы проехать наименьшее суммарное расстояние, грузовики могут брать 4, 3 или 2 ящика. Простым перебором это сильно просто, я думал может есть что то сделать, там например сделать из графа такой чтобы можно было топологически отсортировать, короче как то только не перебором
0
11.02.2015, 20:34
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.02.2015, 20:34

алгоритм поиска повторений
народ, подскажите алгортм для нахождения неизвестных на перед повторений символов в строке

Посоветуйте алгоритм поиска.
Добрый день, есть файл: key(int) value(string) 1217452 745A41B851 3179521 84B41C8719...

Алгоритм поиска в игре
Игра на основе сетки(массив, в каждой ячейке хранится один юнит). Есть наброски алгоритмов, но...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.