Tantangan optimasi algoritma tercepat

9

Ini adalah percobaan pertama saya dengan tantangan kompleksitas asimptotik meskipun saya senang dengan jawaban sepenuhnya dalam kode selama mereka datang dengan penjelasan tentang kompleksitas waktu mereka.

Saya memiliki masalah berikut.

Pertimbangkan tugas T_1, ... T_n dan procs M_1, ..., M_m. Setiap tugas membutuhkan sejumlah waktu untuk melakukan tergantung pada procs.

Setiap tugas juga membutuhkan biaya untuk melakukan tergantung pada procs.

Tugas-tugas harus dilakukan dalam urutan yang ketat (mereka tidak dapat dilakukan secara paralel) dan perlu waktu untuk mengubah proc. Tugas tidak dapat dipindahkan dari satu proc ke proc lain setelah dimulai.

Akhirnya, setiap tugas harus diselesaikan pada waktu tertentu.

tugas

Tujuannya adalah untuk memberikan algoritma (atau beberapa kode) yang diberikan lima tabel dari formulir di atas, meminimalkan total biaya untuk menyelesaikan semua tugas sambil memastikan semua tugas selesai dengan tenggat waktu mereka. Jika ini tidak mungkin, kami hanya melaporkan bahwa itu tidak dapat dilakukan.

skor

Anda harus memberikan kompleksitas Oh yang besar dari solusi Anda dalam hal variabel n, m dan d, di mana d adalah batas waktu terakhir. Seharusnya tidak ada konstanta yang tidak perlu dalam kompleksitas Oh Anda yang besar. Jadi O (n / 1000) harus ditulis sebagai O (n), misalnya.

Skor Anda dihitung hanya dengan menetapkan n = 100, m = 100 dan d = 1000 ke dalam kompleksitas yang Anda nyatakan. Anda ingin skor sekecil mungkin.

pemutus dasi

Dalam kasus seri, jawaban pertama menang.


catatan ditambahkan

log dalam kompleksitas waktu jawaban akan diambil basis 2.

papan skor

  • 10 ^ 202 dari KSFT ( Python ) Pertama kali diserahkan sehingga mendapat hadiah.
  • 10 ^ 202 dari Dominik Müller ( Scala )

sumber
"mengalihkan waktu dari mesin baris ke mesin kolom" Maksud Anda biaya waktu untuk beralih dari M_1 ke M_2? Juga apa perbedaan antara "biaya pengalihan" dan "waktu pengalihan". Mereka biasanya berarti hal yang sama dalam kaitannya dengan menggambarkan algoritma penjadwalan.
Luminous
@ Luminous Pikirkan waktu dalam hitungan detik dan biaya dalam dolar. Mereka berbeda dalam pertanyaan ini. Tabel menunjukkan waktu (biaya masing-masing) dari mesin ganti untuk melakukan tugas selanjutnya. Ini bisa dari M_1 hingga M_2 atau dari M_2 ke M_1.
Ok, itu mengklarifikasi itu.
Luminous
Jawaban singkatnya adalah kompleksitasnya O(m ^ n). Tidak ada algoritma yang "lebih cepat" dari itu. Pemangkasan berdasarkan waktu atau biaya maksimum yang diperlukan tidak mengubah kompleksitas algoritme, juga tidak memiliki biaya dolar dan biaya waktu, karenanya dbukan merupakan elemen kompleksitas.
Bob Dalgleish
1
@ BobDalgleish Itu memberi skor 100 pangkat 100. Saya yakin Anda bisa melakukan jauh lebih baik.

Jawaban:

2

Nilai: 10 ^ 202

Saya agak berharap kami memiliki dukungan LaTeX sekarang ...

Karena tidak ada orang lain yang menjawab, saya pikir saya akan mencoba, meskipun tidak terlalu efisien. Saya tidak yakin apa O besar itu, meskipun.

Saya pikir itu berhasil. Setidaknya, itu berlaku untuk satu-satunya test case yang diposting.

Dibutuhkan input seperti dalam pertanyaan, kecuali tanpa label nomor mesin atau tugas, dan dengan titik koma alih-alih jeda baris.

import itertools
time = [[int(j) for j in i.split()] for i in raw_input().split(";")]
cost = [[int(j) for j in i.split()] for i in raw_input().split(";")]
nmachines=len(time)
ntasks=len(time[0])
switchtime = [[int(j) for j in i.split()] for i in raw_input().split(";")]
switchcost = [[int(j) for j in i.split()] for i in raw_input().split(";")]
deadline = [int(i) for i in raw_input().split()]
d={}
m=itertools.product(range(nmachines),repeat=ntasks)
for i in m:
    t=-switchtime[i[-1]][i[0]]
    c=-switchcost[i[-1]][i[0]]
    e=0
    meetsdeadline=True
    for j in range(ntasks):
        t+=switchtime[i[e-1]][i[e]]+time[i[e]][j]
        c+=switchcost[i[e-1]][i[e]]+cost[i[e]][j]
        e+=1
        if t>deadline[j]:
            meetsdeadline=False
    if meetsdeadline:
        d[(c,t)]=i
print min(d.keys()),d[min(d.keys())]
KSFT
sumber
Bisakah Anda memberikan beberapa penjelasan dan mengatakan skor Anda seharusnya? Juga, dapatkah Anda menunjukkan apa yang diberikannya untuk contoh dalam pertanyaan?
Seperti yang saya nyatakan dalam jawaban saya, saya sudah mencobanya dan itu berhasil pada contoh. Saya tidak yakin apa O besar (yang saya maksudkan dalam jawaban saya).
KSFT
Pada dasarnya, kira-kira berapa banyak operasi yang diperlukan untuk menyelesaikannya. Sepertinya butuh waktu ntasks * m kira-kira (menganggap semua tugas dalam loop mengambil waktu konstan) yang membuat saya curiga tentang kebenarannya saya harus mengakui. Bisakah Anda mengatakan sesuatu tentang mengapa Anda pikir itu berhasil?
1
Oh! Saya melewatkan itu. Jadi m sebenarnya dari ukuran mesin ^ ntasks. OK sekarang saya percaya itu berfungsi. Saya pikir skor Anda adalah (100 ^ 100) * 100.
4
@Lembik Ini memiliki skor terbaik sejauh ini!
KSFT
1

Periksa Semua - Scala

Perkiraan skor: 2m ^ n

Saya mulai dari setiap mesin dan beralih ke semua tugas untuk membuat semua permutasi melalui tugas dengan mesin yang berbeda yang memenuhi tenggat waktu. Berarti jika semuanya dalam waktu saya akan mendapatkan 9 kemungkinan jalur dengan 2 mesin dan 3 tugas. (m ^ n) Setelah itu, saya mengambil jalur dengan biaya terendah.

Input disusun seperti ini (-> menjelaskan bagian-bagiannya dan karenanya tidak boleh dimasukkan):

M_1:5 3 5 4;M_2:4 2 7 5                 --> time
M_1:5 4 2 6;M_2:3 7 3 3                 --> cost
M_1:M_1}0 M_2}1;M_2:M_1}2 M_2}0         --> switch itme
M_1:M_1}0 M_2}2;M_2:M_1}1 M_2}0         --> switch cost
5 10 15 20                              --> deadlines

Dan ini kodenya:

package Scheduling

import scala.io.StdIn.readLine

case class Cost(task: Map[String, List[Int]])
case class Switch(machine: Map[String, Map[String, Int]])
case class Path(time: Int, cost: Int, machine: List[String])

object Main {

    def main(args: Array[String]) {
        val (machines, cost_time, cost_money, switch_time, switch_money, deadlines) = getInput

        val s = new Scheduler(machines, cost_time, cost_money, switch_time, switch_money, deadlines)
        s.schedule
    }

    def getInput(): (List[String], Cost, Cost, Switch, Switch, List[Int]) = {
        val cost_time = Cost(readLine("time to complete task").split(";").map{s => 
                val parts = s.split(":")
                (parts(0) -> parts(1).split(" ").map(_.toInt).toList)
            }.toMap)

        val cost_money = Cost(readLine("cost to complete task").split(";").map{s => 
                val parts = s.split(":")
                (parts(0) -> parts(1).split(" ").map(_.toInt).toList)
            }.toMap)

        val switch_time = Switch(readLine("time to switch").split(";").map{s => 
                val parts = s.split(":")
                (parts(0) -> parts(1).split(" ").map{t =>
                        val entries = t.split("}")
                        (entries(0) -> entries(1).toInt)
                    }.toMap)
            }.toMap)

        val switch_money = Switch(readLine("time to switch").split(";").map{s => 
                val parts = s.split(":")
                (parts(0) -> parts(1).split(" ").map{t =>
                        val entries = t.split("}")
                        (entries(0) -> entries(1).toInt)
                    }.toMap)
            }.toMap)

        val deadlines = readLine("deadlines").split(" ").map(_.toInt).toList

        val machines = cost_time.task.keys.toList

        (machines, cost_time, cost_money, switch_time, switch_money, deadlines)
    }
}

class Scheduler(machines: List[String], cost_time: Cost, cost_money: Cost, switch_time: Switch, switch_money: Switch, deadlines: List[Int]) {

    def schedule() {
        var paths = List[Path]()
        var alternatives = List[(Int, Path)]()

        for (i <- machines) {
            if (cost_time.task(i)(0) <= deadlines(0)) {
                paths = paths ::: List(Path(cost_time.task(i)(0), cost_money.task(i)(0), List(i)))
            }
        }

        val allPaths = deadlines.zipWithIndex.tail.foldLeft(paths)((paths, b) => paths.flatMap(x => calculatePath(x, b._1, b._2)))

        if (allPaths.isEmpty) {
            println("It is not possible")
        } else {
            println(allPaths.minBy(p=>p.cost).machine)
        }
    }

    def calculatePath(prev: Path, deadline: Int, task: Int): List[Path] = {
        val paths = machines.map(m => calculatePath(prev, task, m))
        paths.filter(p => p.time <= deadline)
    }

    def calculatePath(prev: Path, task: Int, machine: String): Path = {
        val time = prev.time + switch_time.machine(prev.machine.last)(machine) + cost_time.task(machine)(task)
        val cost = prev.cost + switch_money.machine(prev.machine.last)(machine) + cost_money.task(machine)(task)

        Path(time, cost, prev.machine :+ machine)
    }
}

Saya juga punya ide untuk memulai dari belakang. Karena Anda selalu dapat memilih mesin dengan biaya terendah jika waktunya lebih kecil maka selisih dari tenggat waktu sebelumnya ke yang baru. Tapi itu tidak akan mengurangi runtime maksimal jika tugas dengan biaya yang lebih baik membutuhkan waktu lebih lama dari batas waktu terakhir.

Memperbarui

======

Berikut ini adalah pengaturan lainnya. waktu:

M_1 2 2 2 7
M_2 1 8 5 10

biaya:

M_1 4 4 4 4
M_2 1 1 1 1

beralih waktu:

    M_1 M_2
M_1  0   2
M_2  6   0

biaya beralih:

    M_1 M_2
M_1  0   2
M_2  2   0

tenggat waktu:

5 10 15 20

Sebagai masukan ke dalam program saya:

M_1:2 2 2 7;M_2:1 8 5 10
M_1:4 4 4 4;M_2:1 1 1 1
M_1:M_1}0 M_2}2;M_2:M_1}6 M_2}0
M_1:M_1}0 M_2}2;M_2:M_1}2 M_2}0
5 10 15 20

Yang ini memiliki dua solusi: waktu: 18, biaya: 15, jalur: Daftar (M_1, M_1, M_1, M_2) waktu: 18, biaya: 15, jalur: Daftar (M_2, M_1, M_1, M_1, M_1)

Yang menimbulkan pertanyaan bagaimana ini harus ditangani. Haruskah semua dicetak atau hanya satu? Dan bagaimana jika waktunya akan berbeda? Apakah satu dengan biaya terendah dan tidak ada tenggat waktu yang terlewat atau haruskah itu juga dengan waktu terendah?

Dominik Müller
sumber
Pertanyaannya mengatakan bahwa tujuannya adalah untuk "[meminimalkan] total biaya". Omong-omong, dapatkah Anda meringkas cara kerja algoritma Anda? Saya tidak tahu Scala, dan saya tidak tahu cara kerjanya.
KSFT
Iterasi semua jalur membutuhkan O(m^n)waktu. Iterasi setiap mesin untuk semua tugas membutuhkan O(n*m^n)waktu.
KSFT
Apakah tidak O(n*m^n)mengulangi setiap tugas untuk masing-masing jalur? Dan mengulangi setiap mesin seperti untuk setiap tugas O(n*m).
Dominik Müller
Ah, salah ketik. Saya bermaksud menulis "Iterasi setiap mesin untuk semua jalur yang diambil O(n*m^n)".
KSFT
Tunggu, tidak, ini O(m*m^n)=O(m^n+1). Namun, skornya masih sama.
KSFT