Traveling Salesperson | JavaScript 程式專案

{"id":27776,"student_id":2591,"content":"setBackdrop(\"black\");\nvar record = 100000;\nvar recordl = [];\nvar s = false;\nvar pen = pen;\npen.color = \"white\";\nvar am = 10;\nvar cities = [];\nfunction createRandCity () {\n    var city = createSprite(\"city.png\");\n    city.x = Math.random()*640;\n    city.y = Math.random()*480;\n    cities.push(city);\n}\n\nfor (var i = 0; i \u003c am; i++) createRandCity();\n\nvar population = [];\nvar children = [];\nvar mutationRate = 0.1;\nvar size = 200;\nvar interval = 10;\n\nwhile (population.length \u003c size) {\n    randomDNA();\n}\n\nfunction randomDNA() {\n    var l = [];\n    while (l.length \u003c am) {\n        var c = Math.floor(Math.random()*am);\n        if (l.indexOf(c) == -1) {\n            l.push(c);\n        }\n    }\n    population.push(l);\n}\n\nfunction matepool() {\n    fitness();\n    for (var i = 0; i \u003c size; i++) {\n        crossover(population[Math.floor(Math.random() * size/2)], population[Math.floor(Math.random()) * size/2]);\n    }\n    if (s) {\n        recordl = population[0];\n        s = false;\n    }\n    population = children;\n    children = [];\n}\n\nfunction fitness() {\n    population.sort(function(a, b) {\n        var ad = 0;\n        var ap = cities[a[0]];\n        var bd = 0;\n        var bp = cities[b[0]];\n        for (var i = 1; i \u003c am; i++) {\n            ad += ap.distanceTo(cities[a[i]]);\n            ap = cities[a[i]];\n            bd += ap.distanceTo(cities[b[i]]);\n            bp = cities[b[i]];\n        }\n        if (ad \u003c record) {\n            record = ad;\n            s = true;\n        }\n        return ad - bd;\n    });\n}\n\nfunction crossover(a, b) {\n    var c = [];\n    var y = b.slice(0);\n    var mid = Math.floor(Math.random()*am);\n    for (var i = 0; i \u003c am; i++) {\n        if (i \u003c mid) {\n            c.push(a[i]);\n            y.splice(y.indexOf(a[i]), 1);\n        } else {\n            if (c.indexOf(y[i-mid]) == -1) {\n                c.push(y[i-mid]);\n            } else {\n                c.push(a[i]);\n            }\n        }\n        if (Math.random() \u003c mutationRate) {\n            var j = Math.floor(Math.random()*i);\n            var k = Math.floor(Math.random()*i);\n            var l = c[j];\n            c[j] = c[k];\n            c[k] = l;\n        }\n    }\n\n    children.push(c);\n}\n\n\nforever(function() {\n    matepool();\n    print(record, 0, 0, \"white\");\n    for (var i = 0; i \u003c am - 1; i++) {\n        var a = cities[recordl[i]];\n        var b = cities[recordl[i + 1]];\n        pen.drawLine(a.x, a.y, b.x, b.y);\n    }\n});","created_at":"2018-05-04T12:37:27.637+08:00","updated_at":"2019-10-12T04:31:52.490+08:00","name":"Traveling Salesperson","language":"javascript","screenshot":{"url":"https://cdn8.koding.school/uploads/project/screenshot/27776/adbaab532555fdf8b60bb0d89a2637e8.jpg"},"parent_id":2,"plugin":"","description":null,"note":null,"status":"public","like_student_ids":[],"is_featured":false,"views":115,"hashid":"rdvs4eey","is_content_changed":false,"review_status":"unsubmitted","submitted_at":null,"reviewed_at":null,"advise":null,"is_deleted":false}