VPF::Нахождение наикратчайшего пути

julia0810

Дата 29.12.2009, 16:41 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 6
Регистрация: 25.12.2009

Репутация: нет
Всего: нет

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

Код



import java.util.List;
import java.util.Vector;
/* описание класса, представляющего собой взвешенный неориентированный граф,
 * где в качестве весов взят наименее загруженный маршрут между 2 районами, в 
 * качестве вершин - названия районов
 */
public class Map {
     public static int [][] graf = { //граф загруженности дорог
            {-1,2,3,2,-1},
            {2,-1,1,3,1},
            {3,1,-1,1,3},
            {2, 3, 1 ,-1, 2},
            {-1,1,3,2,-1} };
     
    private  List edges;
    //метод обновляет или добовляет информацию о загруженности дорог между районами
    public void addBackupinfo(String place1, String place2, int backup)
    {
        //сдесь должна добавлятся информция о пробке
        
    }
    //метод добавления связи между 2 районами
    public void addEdge(String place1, String place2)
    {
       //здесь не знаю как написать подскажите как 
//здесь должно быть добавление связи между двумя районами place1 и place2 
//с помощью массива и пополнять список с помощью add
//и как то должно учитываться что если информация о пробке отсутствует то bacrup=-1 
//еще известно что может быть не более одной связи между 2 точками place
    }
    //метод возвращяет информацию о загружености дорог
    public void    getAverageBackup ()
    {
        graf[0][0]=backup; //обновляет информацию о дпробках
    }
    //описать List
    public  void generatePath (  int place1, int place2) //это генерация пути
    {
        
    seachPath sp;
        sp = new seachPath();
        sp.tempMin = new int [graf.length];
        sp.backup =0;
        sp.graf=graf;
        sp.start= place1; //номер района отправки
        sp.stop = place2; //номер района назначения
        sp.fSeachPath(-1,0,""+sp.start);
    }
}

class seachPath 
{
    int backup; //создание целочисленной переменной которая показывает загруженность дорог
    int[] tempMin; //одномерный массив, куда заносится продолжительность стояния в пробке
    static int[][]graf; //неизменный двумерный массив
    static int start, stop;
    /*функция поиска маршрута*/
    int fSeachPath (int current, int min , String path)
    {
        if (backup !=0 &&backup <min) 
            return backup;
        if (current == stop && (backup ==0|| backup>=min))
        {
            backup=min;
            tempMin[current]=min; //запоминаем время
        //ввыводим начало и конец пути, сколько мин займет путь между районами и через какие надо будет ехать
            System.out.println(start+" ; "+ stop+ " ; " +min+ " ; " + path);
            return backup;
        }
        if(current==-1) 
        {
            current = start ; tempMin[current] = min;
        }
        else if (current != start && (tempMin[current]==0 ||tempMin[current]>min))
        tempMin [current] = min;
        else return backup;
        //для каждой точки найдем мин время в пути до конечной точки и возможные варианты объезда
        for (int i=0; i<graf.length; i++) if (graf[i][current] !=1)
            fSeachPath(i, min +graf[current] [i], path +" ; "+i);
        return backup;
    }

// метод который содержим 2 связанных между собой района и информацию по загружености
class Edge{
    public String[] points ;
    public int backup;
//метод с 2 параметрами, который позволяет связать 2 района и указать загруженость между ними
    public Edge (String place1, String place2, int backup)
    {
        //в этом методе у меня также возникли проблемы
    }
    // метод получающий место нахождения
    public String[] getPoints()
    {
        return points;
    }
    // метод получающий загруженость дороги
    public int getBackup()
    {
        return backup;
    }
    //метод устанавливает степень загруженности маршрута между двумя пунктами в виде числа
    public void setBackup(int backup)
    {
        //помогите описать и этот метод
    }
}
}

MisterCleric

Дата 29.12.2009, 16:54 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1043
Регистрация: 16.2.2006
Где: Харьков, Украина

Репутация: 5
Всего: 38

Привет. Это "задача о кратчайшем пути" или "Задача комивояжера".
Ничего больше подсказать не могу. Давно это было... Надо книжки перечитывать. Поройся в инэте - авось да что-то найдешь

--------------------

ПРИШЕЛ, УВИДЕЛ - ПЕРЕПИСАЛ...

sergioK

Дата 29.12.2009, 18:20 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Awaiting Authorisation
Сообщений: 207
Регистрация: 15.2.2008

Репутация: нет
Всего: нет

Цитата(MisterCleric @ 29.12.2009, 16:54)

не понимаю какое данный вопрос имеет отношение к J2EE ?

MaxPayneC

Дата 29.12.2009, 18:28 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 324
Регистрация: 18.2.2006

Репутация: 5
Всего: 9

Данная задача решается с помощью алгоритма Дейкстра, который ищет стоимость кратчайшего пути в графе в смысле сумм стоимостей ребер и сам путь, при условии что стоимость пути по каждому ребру неотрицательна за время O(n^2), где n - количество вершин в графе. Когда я занимался олимпиадным программированием, граф мы задавали с помощью матрицы весов.

Читать про алгоритм тут: http://ru.wikipedia.org/wiki/%D0%90%D0%BB%...%82%D1%80%D1%8B

julia0810

Дата 30.12.2009, 16:45 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 6
Регистрация: 25.12.2009

Репутация: нет
Всего: нет

Здесь не нужна такие сложные алгоритмы. Просто я не понимаю как описать некоторые методы, например в методе addEdge нужно создать Edge с помощью конструктора publicEdge(String place1,
String place2, int backup) и передать параметры place1, place2 -(-1) , а если есть информация передать ее,т. е. backup.
Подскажите как это сделать smile

вот подправленный код

Код


import java.util.Iterator;
import java.util.List;
import java.util.Vector;
/* описание класса, представляющего собой взвешенный неориентированный граф,
 * где в качестве весов взят наименее загруженный маршрут между 2 районами, в 
 * качестве вершин - названия районов
 */
public class Map {
     public static int [][] graf = {
            {-1,2,3,2,-1},
            {2,-1,1,3,1},
            {3,1,-1,1,3},
            {2, 3, 1 ,-1, 2},
            {-1,1,3,2,-1} };
    
    private  List edges;
    //метод обновляет или добовляет информацию о загружености дорог между районами
    public void addBackupinfo(String place1, String place2, int backup)
    {
        graf[0][0]=backup;
        
    }
    //метод добавления связи между 2 районами
    public void addEdge(String place1, String place2)
    {
        

    }
    //метод возвращяет информацию о загружености дорог
    public void    getAverageBackup ()
    {
        
    }
    
    seachPath sp;
    public  void generatePath (  int place1, int place2)
    {
        for (int i = 0; i < graf.length; i++)
                {
                    for (int j = i+1; j < graf.length; j++)
                    {
                         
    
        sp = new seachPath();
        sp.tempMin = new int [graf.length];
        sp.backup =0;
        sp.graf=graf;
        sp.start= place1; //номер района отправки start
        sp.stop = place2; //номер района назначения stop
        sp.fSeachPath(-1,0,""+sp.start);
    }
}
    }
class seachPath 
{
    int backup; //создание целочисленной переменной которая показывает загруженность дорог
    int[] tempMin; //одномерный массив, куда заносится продолжительность стояния в пробке
     int[][]graf; //неизменный двумерный массив
     int start, stop;
    /*функция поиска маршрута*/
    int fSeachPath (int current, int min , String path)
    {
        if (backup !=0 &&backup <min) 
            return backup;
        if (current == stop && (backup ==0|| backup>=min))
        {
            backup=min;
            tempMin[current]=min; //запоминаем время
        //ввыводим начало и конец пути, сколько мин займет путь между районами и через какие надо будет ехать
            System.out.println(start+" ; "+ stop+ " ; " +min+ " ; " + path);
            return backup;
        }
        if(current==-1) 
        {
            current = start ; tempMin[current] = min;
        }
        else if (current != stop && (tempMin[current]==0 ||tempMin[current]>min))
        tempMin [current] = min;
        else return backup;
        //для каждой точки найдем мин время в пути до конечной точки и возможные варианты объезда
        for (int i=0; i<graf.length; i++) if (graf[i][current] !=1)
            fSeachPath(i, min +graf[current] [i], path +" ; "+i);
        return backup;
    }
}
// метод который содержим 2 связанных между собой района и информацию по загружености
class Edge{
    public String[] points ;
    public int backup;
    public String place1, place2;
//метод с 2 параметрами, который позволяет связать 2 района и указать загруженость между ними
    public Edge (String place1, String place2, int backup)
    {
        /*оставить там только создание членов класса points и backup.*/
        this.place1=place1;
        this.place2=place2;
        this.backup=backup;
        
    }
    // метод получающий место нахождения
    public String[] getPoints()
    {
        return points;
    }
    // метод получающий загруженость дороги
    public int getBackup()
    {
        return backup;
    }
    //метод устанавливает степень загруженности маршрута между двумя пунктами в виде числа
    public void setBackup(int backup)
    {
          graf[0][0] = backup ; 
    }
}

}

MaxPayneC

Дата 30.12.2009, 20:37 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 324
Регистрация: 18.2.2006

Репутация: 5
Всего: 9

Насколько я понял ваше описание задачи, алгоритм Дейкстра все-таки требуется. И на вопрос про ребра я уже отвечал, матрица весов, такая что weight[i][j] есть вес ребра из вершины i в вершину j.

jk1

Дата 30.12.2009, 21:04 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 1168
Регистрация: 17.10.2008
Где: Санкт-Петербург

Репутация: 40
Всего: 75

Вот тут есть реализация алгоритма Дейкстры на java, читающая матрицу весов из файла.

--------------------

Opinions are like assholes — everybody has one

julia0810

Дата 31.12.2009, 10:33 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 6
Регистрация: 25.12.2009

Репутация: нет
Всего: нет

jk1 спасибо я думаю этот алгоритм мне поможет. А подскажите пожайлуйста как мои переменные place1 и place2 формата String переделать в формат int.

MaxPayneC

Дата 31.12.2009, 10:54 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 324
Регистрация: 18.2.2006

Репутация: 5
Всего: 9

Код


String s = "123";
try
{
int x = Integer.parseInt(s);
}
catch (NumberFormatException ex)
{
System.out.println("s is not a number");
}

Это сообщение отредактировал(а) MaxPayneC - 31.12.2009, 10:55

julia0810

Дата 31.12.2009, 13:11 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 6
Регистрация: 25.12.2009

Репутация: нет
Всего: нет

MaxPayneC спосибо тебе огромное.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Java: Общие вопросы \| Следующая тема »