Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/8: Рейтинг темы: голосов - 8, средняя оценка - 4.75
Влад000
0 / 0 / 0
Регистрация: 05.12.2010
Сообщений: 64
#1

Использование алгоритма поиска с возвратом

26.01.2013, 18:06. Просмотров 1481. Ответов 11
Метки нет (Все метки)

Добрый день, помогите пожалуйста решить проблему. Очень долго не могу составить правильную функцию для работы программы( Надо написать псевдокод для такой программы: (задача во вложении).
Я написал такой код:
STAN(min:number=0(минимальное время), temp:array[](временной массив),
diffs:array[][](таблица со временем, diffs[a][b] - время перемещения
между станциями a и b), station_index (Индекс станции), s1,s2
(пользовательское значение - станция отправки и станция прибытия));

function main():void //Главная функция
{
повторяем (i = 0; i < n; i++) //Бежим по всем станциям
{
temp.push(diffs[s1][i] + diffs[i][s2]);//Забиваем во временный массив кандидата на минимальное время
если (isMinimal(diffs[s1][i] + diffs[i][s2]))//Если оно на данном этапе действительно минимально
{
min = diffs[s1][i] + diffs[i][s2];//Забиваем как минимальное
station_index = i;//Сохраняем индекс станции
}
}
вывод (min, station_index);//Выводим время и станцию, через которую ехать
}
function isMinimal(value:Number):Boolean //Возвращет, является ли value наименьшим во временном массиве
{
повторяем ( i = 0; i < temp.length; i++)//Бежим по временному массиву
{
если (value > temp[i]) return false; //Если вдруг value больше какого-то элемента, значит оно не минимально
}
return true;
}
Проблема в том, что эта программа не учитывает того, что между станциями А и В может быть несколько связующих станций и может быть такой вариант, что такого пути нет. Для этого надо использовать поиск с возвратом, но я уже раз 5 показывал свои варианты преподу и он все отметает, говорит что ваще не то.
Ошибка начинается со строки temp.push(diffs[s1][i] + diffs[i][s2]) (нужно написать нужную функцию,но я не знаю какую) Помогите кто чем может и какие варианты можно попробовать.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.01.2013, 18:06
Ответы с готовыми решениями:

Алгоритм поиска алгоритма
Здравствуйте! Хочу написать программу которая будет искать алгоритм который...

Составить блок-схему алгоритма поиска всех клеток, находящихся под ударом ферзя
Составить блок-схему алгоритма следующей задачи: Даны координаты ферзя,...

Составить блок-схему алгоритма поиска всех троек натуральных чисел, удовлетворяющих условию
Составить блок-схему алгоритма следующей задачи: Дано натуральное число m....

Составить блок-схему алгоритма поиска частного и остатка от деления одного числа на другое
Составить блок-схему алгоритма следующей задачи: Даны натуральные числа a и b,...

Алогоритм поиска поиска покрывающего дерева (Minimal Ratio Spanning Tree)
Задача которую мне необходимо решить сводится к нахождению Minimal Ratio...

11
Влад000
0 / 0 / 0
Регистрация: 05.12.2010
Сообщений: 64
30.01.2013, 18:47  [ТС] #2
Люююди, откликнитесь кто-нибудь, пожалуйста!
0
Taatshi
Администратор
11709 / 5052 / 257
Регистрация: 05.04.2011
Сообщений: 13,803
Записей в блоге: 2
03.02.2013, 11:26 #3
Влад000, перепечатайте задание на форум.
0
Влад000
0 / 0 / 0
Регистрация: 05.12.2010
Сообщений: 64
04.02.2013, 09:22  [ТС] #4
Задание: Некоторая железнодорожная компания обслуживает n станций S1, S2, ..., Sn. Она предполагает установить информационные терминалы, с которых клиент может вводить название своей станции отправления Sa и станции назначения Sb, а ему должно выдавать расписание поездов, обеспечивающих минимальное время поездки. Написать алгоритм, который позволит это осуществить. Расписание представлено данными некоторой структуры, где перечисляется время отправления (прибытия) всех поездов (не между всеми станциями есть прямое сообщение). (Указание: использовать "поиск с возвратом")
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
04.02.2013, 13:34 #5
Задайте сам граф, напр матрицей смежности. Напр первая строка

-1 2 -1 3

Значит из первой станции можно приехать во 2-ю за 2 часа или в 4-ю за 3 часа. А дальше просто крутите рекурсию

C++
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
void Step(
 int * path,   // пройденный путь
 int num,  // число пройденных станций
 int len )     // пройденное время 
{
 int row = path[num - 1];
 for (int i = 0; i < N; ++i) {
  if (a[row][i] <= 0) continue;
 
// проверяем след станция уже была
  int j;
  for (ij = 0; j < num; ++j)  
   if (i == path[j]) break;
  if (j < num) continue;
 
// делаем шаг
  path[num++] = i;
  len += a[row][i];
 
// нашли путь, проверяем и запоминаем если лучший (сделаете сами)
  if (i == lastStation) {
   ..
  } 
  else 
   Step(path, num, len);  // рекурс
  
// возвращаем шаг
  --num;
  len -= a[row[[i]; 
 }
}
0
Влад000
0 / 0 / 0
Регистрация: 05.12.2010
Сообщений: 64
04.02.2013, 16:44  [ТС] #6
-1 2 -1 3 - не очень понимаю, почему -1 задана станция?
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
04.02.2013, 17:04 #7
Цитата Сообщение от Влад000 Посмотреть сообщение
-1 2 -1 3 - не очень понимаю, почему -1 задана станция?
Значит трамваи не ходют из первой в первую и из первой в третью
0
Влад000
0 / 0 / 0
Регистрация: 05.12.2010
Сообщений: 64
04.02.2013, 19:20  [ТС] #8
// нашли путь, проверяем и запоминаем если лучший (сделаете сами)
то есть создаем одномерный массив, в который будут записываться -1 2 -1 3 и прочие станции?
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
04.02.2013, 19:35 #9
Цитата Сообщение от Влад000 Посмотреть сообщение
// нашли путь, проверяем и запоминаем если лучший (сделаете сами)
то есть создаем одномерный массив, в который будут записываться -1 2 -1 3 и прочие станции?
Нет, просто индексы станций,
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
i
int bestPath[N];
int numBest = 0;
int bestLen = -1;
const int firstStation = 2;  // исходная станция (индекс)
const int lastStation = 5;  // конечная  (индекс)
 
nt main( void )
{
 int path[N];
 path[0] = firstStatin;
 Step(path, 1, 0);
 return; 
}
0
Влад000
0 / 0 / 0
Регистрация: 05.12.2010
Сообщений: 64
06.02.2013, 15:47  [ТС] #10
int j;
for (ij = 0; j < num; ++j)
if (i == path[j]) break;
if (j < num) continue;
не могу понять, почему в цикле for (ij = 0; j < num; ++j) , ij=0

Добавлено через 11 минут
i
int bestPath[N];
int numBest = 0;
int bestLen = -1;
const int firstStation = 2; // исходная станция (индекс)
const int lastStation = 5; // конечная (индекс)
и почему такие числа приравниваются? не могу понять.
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
06.02.2013, 16:28 #11
Цитата Сообщение от Влад000 Посмотреть сообщение
int j;
и почему такие числа приравниваются? не могу понять.
Если есть "станции", Вы так или иначе храните их в виде массива (в общем случае контейнера). Как Вы зададите станцию с которой начинаете? Индексом (порядковым номером) в массиве. Как Вы напечатаете найденный маршрут? Массивом индексов, напр {2, 0, 1, 5}

Влад, что-то совсем мрачно - видать гульки на уме а не программирование Больше на вопросы типа "ничего не понимаю" отвечать не буду
0
Влад000
0 / 0 / 0
Регистрация: 05.12.2010
Сообщений: 64
06.02.2013, 18:15  [ТС] #12
Спасибо. Просто я задачу саму понять не мог в плане того, как должен выглядеть конечный ответ.

Добавлено через 1 минуту
В общем вот:
Код
STEP(*path (пройденный путь), num (число пройденных станций),
len (пройденное время))
{
 row = path[num-1];
  for (i = 0; i < N; i++)
{
 if (a[row][i]<= 0) continue;
// проверяем след станция уже была
  j;
  for (ij = 0; j<num; ++j)
  if (i == path[j]) break;
  if (j < num) continue;
// делаем шаг
path[num++] = i;
len += a[row][i];
// нашли путь, проверяем и запоминаем, если лучший
  if (i == lastStation) {
   int bestPath[N];
int numBest = 0;
int bestLen = -1;
const int firstStation = 2;  // исходная станция (индекс)
const int lastStation = 5;  // конечная  (индекс)
 
nt main( void )
{
 int path[N];
 path[0] = firstStatin;
 Step(path, 1, 0);
 return; 
}
  } 
  else 
   Step(path, num, len);  // рекурс
  
// возвращаем шаг
  --num;
  len -= a[row[[i]; 
 }
}
все так?
0
06.02.2013, 18:15
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.02.2013, 18:15

Понятие трудоёмкости алгоритма. Понятие эффективного алгоритма
Понятие трудоёмкости алгоритма. Классификация алгоритмов на основе функции...

Пояснить суть алгоритма поиска с возвратом
Здравствуйте) Ни как не могу понять &quot;смысл&quot; алгоритма с возвратом... :( Какая у...

Реализуйте на практике 2 алгоритма поиска и 2 алгоритма сортировки. Результаты сравните
Всем привет! Я в С++ абсолютный чайнег, поэтому за дебильные вопросы сапогами...


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

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

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