Софтуерно Инженерство
Loading...
+ Нов въпрос
djc_bg2015 avatar djc_bg2015 922 Точки

[Homework] Greedy Algorithms - Problem 1-5 Въпроси

Здравейте,

подхванах задачите от домашното и се оказва че имам нужда от млако помощ.

Относно задача 2: Подреждам процесите по стойност, но немога да измисля по какъв критерии да сравнявам следващия процес, така че да съм сигурен че ще може да се изпълни ако го добавя в изхода.

Всякаква подсказка ще ми е добре дошла :)

Относно задача 3: Използвам правилото на Warnsdorf, но резултата се разминава  спрямо показаните примери (само на дъската 5 х 5 получавам 1:1 резултат. Изпълнявам всеки ход, взимайки полето с най - млако следващи възможни продължения.). Нормално л ие да има частично разминаване, или това значи че алгоритъма не работи както се очаква?

Благодаря предварително!

 

Тагове:
0
Структури от данни и алгоритми 04/11/2015 14:00:57
Filkolev avatar Filkolev 4501 Точки

На задачата с коня важното е да се запълни дъската. Разминаване може да има ако имаш повече от една клетка с еднаква стойност; при равенство ти може би взимаш по друг критерий клетката. Ако дъската е пълна с правилните числа всичко е наред :)

На 2-ра - това мисля е единствената затрудняваща част от домашното. Не съм я решавал, но ми се върти в главата идея за масив, по някакъв начин да се пазят възможните комбинации. Например, взимаме процеса с най-голяма стойност и го слагаме по индекс на възможно най-крайната позиция; ако не можем (има вече там сложен процес) гледаме предходните позиции и така докато не запълним масива. Не гарантирам, че ще работи, нито че е оптимално. Но е идея, може да пробваш и после да кажеш дали логиката е вярна.

 

0
03/11/2015 20:47:23
djc_bg2015 avatar djc_bg2015 922 Точки

Мерси за отговора :)

Ще се пробвам утре на свежа глава и ще пиша, когато имам резултат.

Поздрави!

0
djc_bg2015 avatar djc_bg2015 922 Точки

Ами направих го по следния начин:

взимам листа с вече добавените таскове и следващия таск, който трябва да се добави.

Слагам всичко в нов лист от таскове (temp), подреждам ги по deadline, и въртя форийч като инкрементирам една променлива step=1. За всяка стъпка проверявам дали елемента който е наред има deadline < step. Ако няма такъв елемент значи новия таск може да бъде добавен, ако пък има такъв елемент брейквам форийча и продължавам към следващия таск.

 

Доста завъртяно стана, но пък изглежда да работи...

0
Ivaka127 avatar Ivaka127 20 Точки

На задача 3та за Knight Tour, има значение в какъв ред проверяваш стойността на потенциалната клетка. Направил съм малко reverse engineering и трите отговора ми се получават 1:1 със следната последователност на ходове от коня:
 

public static int[,] knightMoves = new int[,]
{
    { +1, +2 },
    { -1, +2 },
    { +2, +1 },
    { +1, -2 },
    { -1, -2 },
    { -2, +1 },
    { +2, -1 },
    { -2, -1 }
};


Друго - при изчисляване на броя потенциални ходеве, се взима предвид вече клетките, където конят е минал и те не се смятат.

 

На задача 2ра за Processor Scheduling, на всяка стъпка изчислявам приоритет на всички останали таскове, като изпълнявам таска с най-голям приоритет:
 

double taskPriority = taskValue / (taskDeadline - stepCount);

 

3
04/11/2015 11:53:15
djc_bg2015 avatar djc_bg2015 922 Точки

Ами да, рзбрах, че там е проблема в последствие :)

Ето как проверявам аз в момента (отговорите се разминават):

var possibleMoves = new[]
{
    new {Row = -2, Col = 1},
    new {Row = -1, Col = 2},
    new {Row = 1, Col = 2},
    new {Row = 2, Col = 1},
    new {Row = 2, Col = -1},
    new {Row = 1, Col = -2},
    new {Row = -1, Col = -2},
    new {Row = -2, Col = -1},
};

 

Относно задача 2 - много добре си се сетил :)

0
04/11/2015 12:29:15
krach avatar krach 65 Точки

За задача 3 не мисля че е от ъществено значение дали 5тия ход примерно ще ти е в една или друга клетка, след като резултата е верен. Нямаш в условието на позиция X и Y да е определена стойност, така че....

Моя вариант на 3
https://github.com/krachunov/Algorithms/blob/master/src/homeWork7/KnightTour.java

1
Ivaka127 avatar Ivaka127 20 Точки

Да, колега, прав си, задача 3 има повече от едно вярно решение. Просто ми беше интересно при какви условия ще получа абсолютно същия резултат, малко безмислено от моя страна.

0
04/11/2015 12:59:52
dim4o avatar dim4o 289 Точки

Аз не съм сигурен, че разбирам правилно условието на 2-ра задача. Може ли някой да даде още примери с input/output? Какво пречи да вземем най-големия deadline и толкова на брой пъти да вземем най-високите tasks по стойност и после да сортираме резултата. Защо това няма да работи?

EDIT: Сега се замислих и май схванах какво се иска. Изглежда лесно. Въпреки това ще е полезно да се видят още примери.

0
04/11/2015 17:49:02
moholovka avatar moholovka 169 Точки

https://github.com/IvanMladenov/Algorithms/tree/master/GreedyAlgorithms/ProcessorScheduling

Моето решение на втора, на третия пример последователността е различна но тотала е същия и според мен ще работи вярно при различни входове. В репозиторито има и на първа решение.

 

EDIT: Допълвам и с коня, не ми съвпада с нито един от примерите, но работи вярно, поне за първите два примера го проверих.

https://github.com/IvanMladenov/Algorithms/blob/master/GreedyAlgorithms/KnightsTour/Program.cs

1
05/11/2015 01:31:19
Innos avatar Innos SoftUni Team 419 Точки

Поздравления колега, твоето решение на 2ра задача е най-доброто което видях. Много хитър начин на обхождане, който не само че спазва greedy изискванията, но и ще произвежда най-оптималното решение всеки път, без излишни проверки.

Edit: Само бих сложил 1 проверка точно преди да extract-неш от BinaryHeap-a дали BinaryHeap-a е празен, за да можеш да предотвратиш ситуации от рода на имаш 1 таск с Deadline 5 и 0 с deadline 4, на deadline 5 вкарваш таска и го вадиш в резултатите, но на 4 ако няма нищо и BinaryHeap-а е празен ще гръмне като се опиташ да вадиш.

0
08/11/2015 16:46:50
aanguelov avatar aanguelov 219 Точки

Здравейте, домашното от Greedy Algorithms не е пуснато за оценяване.

0
Filkolev avatar Filkolev 4501 Точки

Да, малко досаден проблем. Сложен е краен срок за оценяване, но като не е избран тип оценяване пак няма как да се оценява. Оправено е вече.

0