Форум программистов, компьютерный форум, киберфорум
PHP для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/6: Рейтинг темы: голосов - 6, средняя оценка - 5.00
0 / 0 / 0
Регистрация: 25.08.2014
Сообщений: 8
1

Посчитать минимальную стоимость пути из города А в город Б

25.08.2014, 19:55. Просмотров 1207. Ответов 10
Метки нет (Все метки)


Есть массив городов .Из каждого города есть маршруты к другим городам .Выглядит этот массив так

PHP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
$list_of_cities[1]- индекс города в массие
$list_of_cities[1]['neighbours'] - количесто маршрутов из города
$list_of_cities[1]['paths'][1] - первый маршрут и т.д.
nr -индекс города,к которому ведет маршрут
cost - условная стоимость маршрута к городу  индекс которого nr (из данного города)
 
//1 city data 'gdansk'
$list_of_cities[1]['city'] = 'gdansk';
$list_of_cities[1]['neighbours'] = 1;//city neighbours
$list_of_cities[1]['paths'][1] = array( 'nr'=>'2','cost'=>'1');//nr - index of a city connected ,cost - the transportation cost
$list_of_cities[1]['paths'][2] = array( 'nr'=>'3','cost'=>'3');
 
//2 city data 'bydgoszcz'
$list_of_cities[2]['city'] = 'bydgoszcz';
$list_of_cities[2]['neighbours'] = 3;
$list_of_cities[2]['paths'][1] = array( 'nr'=>'1','cost'=>'1');
$list_of_cities[2]['paths'][2] = array( 'nr'=>'3','cost'=>'1');
$list_of_cities[2]['paths'][3] = array( 'nr'=>'4','cost'=>'4');
 
//3 city data 'torun'
$list_of_cities[3]['city'] = 'torun';
$list_of_cities[3]['neighbours'] = 3;
$list_of_cities[3]['paths'][1] = array( 'nr'=>'1','cost'=>'3');
$list_of_cities[3]['paths'][2] = array( 'nr'=>'2','cost'=>'1');
$list_of_cities[3]['paths'][3] = array( 'nr'=>'4','cost'=>'1');
 
//4 city data 'warszawa'
$list_of_cities[4]['city'] = 'warszawa';
$list_of_cities[4]['neighbours'] = 2;
$list_of_cities[4]['paths'][1] = array( 'nr'=>'2','cost'=>'4');
$list_of_cities[4]['paths'][2] = array( 'nr'=>'3','cost'=>'1');
ЗАДАЧА.

Написать скрипт, который позволяет посчитать минимальный путь из города 1 в город 2
Например стоимость мин. пути из gdansk в warszawa = 3
или bydgoszcz - warszawa = 2

Как написать функцию для вычисления минимальной стоимости пути ?

Добавлено через 9 часов 15 минут
Народ
Ну не уже ли ни у кого нет идей ?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
25.08.2014, 19:55
Ответы с готовыми решениями:

Нахождение пути из города А в город Х
Написать программу нахождения пути из города А в город Х . Количество городов не менее 10....

Найдите минимальную стоимость пути
На клетчатом поле размером m×n в левом нижнем углу лежит игральная кость. За один ход её можно...

на пути из города A в город B длиной в S километров вероятность остаться без колеса на отрезке в 1 км
Помогите решить вот такую ​​задачу: на пути из города A в город B длиной в S километров вероятность...

Посчитать минимальную и максимальную стоимость проезда в рублях, которую могли заплатить пассажиры автобуса
Цена проезда в автобусах нашего города — один рубль. Однако, не все так просто — каждый взрослый...

10
SV
55 / 55 / 25
Регистрация: 03.08.2014
Сообщений: 258
25.08.2014, 20:02 2
Лучший ответ Сообщение было отмечено for-web1 как решение

Решение

Да простым перебором всех возможных вариантов, у тебя же их мало.
Рекурсией как нефиг делать.
Берешь начальный город и смотришь куда можно поехать. Едешь туда. Если это не пункт назначения то смотришь куда можно поехать из этого города, исключая города которые ты проехал. И так до тех пор пока не приедешь куда надо или пока возможные варианты закончатся.
Получишь набор всех возможных путей добраться из А в Б.
Дальше просто выбираешь самый дешевый.
0
0 / 0 / 0
Регистрация: 25.08.2014
Сообщений: 8
25.08.2014, 23:09  [ТС] 3
Да в том то и дело ,что количество городов может быть и большим .Получается ,что если перебором ,то много вариантов выходит .Ведь с каждого города может быть много маршрутов .А с тех городов ,куда ведут маршруты еще в каждом куча маршрутов .Пробовал рекурсией .Получается бесконечный цикл и скрипт останавливается .

Может есть какие-то супер идеи?
0
SV
55 / 55 / 25
Регистрация: 03.08.2014
Сообщений: 258
25.08.2014, 23:26 4
Цитата Сообщение от for-web1 Посмотреть сообщение
Может есть какие-то супер идеи?
есть потрясающая идея - исправить баги в вашей рекурсии, что бы скрипт не вис.
Слишком много городов это сколько? 50 тысяч? 200 тысяч? или 30 штук?
0
0 / 0 / 0
Регистрация: 25.08.2014
Сообщений: 8
25.08.2014, 23:57  [ТС] 5
20 тыс.

Добавлено через 2 минуты
Поделитесь соображениями по поводу Вашего варианта функции .Хотя бы в базовом ее виде.
0
SV
55 / 55 / 25
Регистрация: 03.08.2014
Сообщений: 258
25.08.2014, 23:57 6
Цитата Сообщение от for-web1 Посмотреть сообщение
20 тыс.
овно вопрос - считаем точно так же как я предложил, но результаты не выбрасываем а сохраняем, например в БД.
Получим следующую таблице
ПунктА - ПунктБ - Цена - Путь

А потом просто обновляем эту таблицу при изменении цен.
А когда пользователь делает запрос - мы ничего не считаем, мы просто делаем запрос к базе. Быстро и эффективно
0
0 / 0 / 0
Регистрация: 25.08.2014
Сообщений: 8
26.08.2014, 00:00  [ТС] 7
Мне бы функцию...

Добавлено через 20 секунд
Код
0
SV
55 / 55 / 25
Регистрация: 03.08.2014
Сообщений: 258
26.08.2014, 00:09 8
Лучший ответ Сообщение было отмечено for-web1 как решение

Решение

Цитата Сообщение от for-web1 Посмотреть сообщение
Поделитесь соображениями по поводу Вашего варианта функции .Хотя бы в базовом ее виде.
PHP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
$all = []; // тута будем хранить все возможные пути
$data = [
  'Moscow' => [
    'to' => [
      'London' => '20 баксов',
      'Питер' => '5 баксов' и т.д.
     ]
  ]
];
 
 
/*
@$current_city - тута название текущего города, в котором мы находимся
@$destination_city - а тута тот город, куда хотим приехать
@$path - тут мы храним путь который мы уже прошли, например в массиве ['Москва', 'Лондон', 'Нью Васюки']
*/
 
function foo($current_city, $destination_city, $path) {
 
$path[] = $current_city; // добавим текущий город в пройденный путь
if($current_city == $destination_city) { // всё, на месте
  $all[] = $path; // сохраним путь
 return;
}
 
 
$c = $data[$current_city]; // взяли инфу по текущему городу
 
foreach($c['to'] as $name=>$value) { // проходимся по всем возможным пунктам назначения
 if(in_array($path, $name)) // если данный город мы уже посещали - то  не поеедм, иначе будем по кольцу ходить. порядок в in_array мог напутать, что там вначале, ключ или массив
   continue
 
  // если в данном городе еще не были - самое время посетить
 
  foo($name, $destination_city, $path); // поехали в следующий город
 
} 
 
}
ну как то так, я конечно это не проверял, но думаю общая логика понятна, экспериментируйте

Добавлено через 22 секунды
Цитата Сообщение от for-web1 Посмотреть сообщение
Мне бы функцию...
откат в пол зарплаты
1
502 bad gateway
Эксперт PHP
4500 / 3661 / 1538
Регистрация: 24.04.2014
Сообщений: 10,783
26.08.2014, 01:11 9
for-web1, эту задачу за тебя уже решили. погугли задача комивояжера
0
0 / 0 / 0
Регистрация: 25.08.2014
Сообщений: 8
26.08.2014, 09:35  [ТС] 10
SV ,спасибо тебе
Видимо в моей функции цикл перебирался по кругу.

Но еще больше меня удивило ,что у меня имена переменных полностью совпадают с твоими .
0
SV
55 / 55 / 25
Регистрация: 03.08.2014
Сообщений: 258
26.08.2014, 14:58 11
Цитата Сообщение от for-web1 Посмотреть сообщение
Но еще больше меня удивило ,что у меня имена переменных полностью совпадают с твоими .
я у тебя подглядывал
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
26.08.2014, 14:58

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь или здесь.

Найти маршрут перелета из города А в город В, не содержащий города С
Нужна помощь с написанием программы про пути в ориентированном графе. Текст задания: Дан список...

Найти для 1-го города кратчайшие пути в другие города
Есть некоторое количество городов, некоторые из которых соединены дорогами известной длины. Вся...

Игра в города. Возвращает только первый встречный город
Написал примитивную игру в города на пшп. Есть массив с городами и две функции,одна определяет...

Можно ли передать как нибудь интернет из города в город?
К примеру с Москвы в Ставрополь? Если такое оборудование чтоб передавало интернет как vpn...

Объехать все города и вернуться в тот город, с которого выехали
Есть несколько городов. все города связаны между собой дорогами . нужно объехать все города и...

Объехать все города и вернуться в тот город, с которого началось путешествие
"Задача о городах». Есть несколько городов. Все города связаны друг с другом дорогами. Нужно...


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

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

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