[Homework] Greedy Algorithms - Problem 1-5 Въпроси - Софтуерен университет

djc_bg2015 923 Точки

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

Здравейте,

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

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

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

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

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

Тагове:

03/11/2015 20:04:58 Структури от данни и алгоритми 04/11/2015 14:00:57

Filkolev 4482 Точки

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

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

03/11/2015 20:36:35 03/11/2015 20:47:23

djc_bg2015 923 Точки

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

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

Поздрави!

04/11/2015 00:42:57

djc_bg2015 923 Точки

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

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

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

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

04/11/2015 09:18:06

Orhan 12 Точки

http://pastebin.com/F0UAKNvQ- това е моето решение на задача 2

03/11/2015 22:30:34

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);

04/11/2015 11:18:45 04/11/2015 11:53:15

djc_bg2015 923 Точки

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

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

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 - много добре си се сетил :)

04/11/2015 12:25:03 04/11/2015 12:29:15

krach 65 Точки

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

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

04/11/2015 12:39:39

Ivaka127 20 Точки

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

04/11/2015 12:59:41 04/11/2015 12:59:52

Покажи всички коментари

dim4o 288 Точки

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

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

04/11/2015 17:33:17 04/11/2015 17:49:02

moholovka 169 Точки

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

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

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

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

05/11/2015 00:19:42 05/11/2015 01:31:19

Innos 419 Точки

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

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

07/11/2015 22:36:59 08/11/2015 16:46:50

dim4o 288 Точки

2-ра се оказа наистина лесна. Трудното беше да разбера правилно условието.

Ето ги моите решения на задачите от домашното: https://github.com/dim4o/Courses/tree/master/10-Algorithms/07-GreedyAlgorithms

05/11/2015 09:56:59 05/11/2015 10:06:08

aanguelov 219 Точки

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

10/11/2015 09:55:21

Filkolev 4482 Точки

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

10/11/2015 14:50:19